package com.platform.modules.alg.alglib.hdu4417;

import java.util.Arrays;

import static java.lang.Math.sqrt;

public class Hdu4417 {
    public final int maxn = 100000;
    int L[] = new int[maxn];
    int R[] = new int[maxn];
    int belong[] = new int[maxn];
    int a[] = new int[maxn];
    int temp[] = new int[maxn];
    int n;
    int m;

    public String output = "";

    void build() {
        int t = (int) sqrt(n);
        int num = n / t;
        if (n % num != 0) num++;
        for (int i = 1; i <= num; i++) {
            L[i] = (i - 1) * t + 1;
            R[i] = i * t;
        }
        R[num] = n;
        for (int i = 1; i <= n; i++)
            belong[i] = (i - 1) / t + 1;
        for (int i = 1; i <= num; i++) {
            // 每块排序
            Arrays.sort(temp, L[i], 1 + R[i]);
        }
    }

    int query(int l, int r, int h) {
        int ans = 0;
        if (belong[l] == belong[r]) {
            for (int i = l; i <= r; i++)
                if (a[i] <= h) ans++;
        } else {
            for (int i = l; i <= R[belong[l]]; i++)//左端
                if (a[i] <= h) ans++;
            for (int i = belong[l] + 1; i < belong[r]; i++)//中间
                ans += upperBound(temp, L[i], R[i] + 1, h) - L[i];
            for (int i = L[belong[r]]; i <= r; i++)//右端
                if (a[i] <= h) ans++;
        }
        return ans;
    }

    /**
     * @param arr   数组
     * @param value 待比较的值
     * @param left  左端点下标
     * @param right 右端点下标
     * @return 第一个大于value的数的坐标
     */
    int upperBound(int[] arr, int left, int right, int value) {
        int l = left, r = right - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (arr[m] <= value) {
                l = m + 1;
            } else {  // arr[m] > value
                r = m - 1;
            }
        }
        return l;
    }

    public String cal(String input) {
        String[] line = input.split("\n");
        String[] num = line[0].split(" ");
        n = Integer.parseInt(num[0]);
        m = Integer.parseInt(num[1]);
        String[] keys = line[1].split(" ");

        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(keys[i - 1]);
            temp[i] = a[i];
        }
        build();
        int j = 0;
        while (m-- > 0) {
            int l, r, h;
            String[] command = line[2 + j].split(" ");
            j++;
            l = Integer.parseInt(command[0]);
            r = Integer.parseInt(command[1]);
            h = Integer.parseInt(command[2]);
            output += query(++l, ++r, h) + "\n";
        }
        return output;
    }
}
